/**
  * @file    :CircleQueue.hpp
  * @brief   :循环队列模板类的实现
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-28
*/

#ifndef _QUEUE_CIRCLEQUEUE_H_
#define _QUEUE_CIRCLEQUEUE_H_

#include "Queue.hpp"
#include <iostream>

template<typename type>
class CircleQueue;

template<typename type>
std::ostream &operator<<(std::ostream &out, const CircleQueue<type> &src);

//循环队列模板
template<typename type>
class CircleQueue : public Queue<type> {

    friend std::ostream &operator<<<>(std::ostream &out, const CircleQueue<type> &src);

private:
    type *_data;  // 数据空间
    int _front;   // 头指针
    int _rear;    // 尾指针
    int _capacity;// 空间大小

public:
    // 指定容量大小的构造函数
    CircleQueue(int capacity = 20) : _front(-1), _rear(-1), _capacity(capacity) {
        this->_data = new type[this->_capacity];
        if (!this->_data) {
            throw std::bad_alloc();
        }
    }

    // 析构函数
    ~CircleQueue() {
        delete[] this->_data;
    }

    // 获取队尾元素
    bool Rear(type &data) {
        if (this->IsEmpty()) {
            return false;
        }

        data = this->_data[this->_rear];

        return true;
    }

    // 清空队列
    void Clear();

    // 判断队列是否满了
    bool IsFull() const;

    // 入队
    virtual bool EnQueue(const type &data);

    // 出队(保存数据)
    virtual bool DeQueue(type &data);

    // 出队(不保存数据)
    virtual bool DeQueue();

    // 获取队头元素
    virtual bool Front(type &data) const;

    // 判断队空
    virtual bool IsEmpty() const;

    // 获取队列长度
    virtual int Length() const;
};


// 清空队列
template<typename type>
void CircleQueue<type>::Clear() {
    this->_rear = -1;
    this->_front = -1;
}

// 判断队列是否满了
template<typename type>
bool CircleQueue<type>::IsFull() const {
    return this->Length() == this->_capacity;
}

// 入队
template<typename type>
bool CircleQueue<type>::EnQueue(const type &data) {
    // 非法处理
    if (this->IsFull()) {
        return false;
    }

    // 空队特殊处理
    if (this->IsEmpty()) {
        _front = 0;
    }

    this->_rear = (this->_rear + 1 + this->_capacity) % this->_capacity;// 更新尾指针
    this->_data[this->_rear] = data;

    return true;
}

// 出队(保存数据)
template<typename type>
bool CircleQueue<type>::DeQueue(type &data) {
    // 空队处理
    if (this->IsEmpty()) {
        return false;
    }

    data = this->_data[this->_front];

    if (this->Length() == 1) {
        this->_front = -1;
        this->_rear = -1;
    } else {
        this->_front = (this->_front + 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 出队(不保存数据)
template<typename type>
bool CircleQueue<type>::DeQueue() {
    // 空队处理
    if (this->IsEmpty()) {
        return false;
    }

    if (this->Length() == 1) {
        this->_front = -1;
        this->_rear = -1;
    } else {
        this->_front = (this->_front + 1 + this->_capacity) % this->_capacity;
    }

    return true;
}

// 获取队头元素
template<typename type>
bool CircleQueue<type>::Front(type &data) const {
    if (this->IsEmpty()) {
        return false;
    }

    data = this->_data[this->_front];

    return true;
}

// 判断队空
template<typename type>
bool CircleQueue<type>::IsEmpty() const {
    return this->Length() == 0;
}

// 获取队列长度
template<typename type>
int CircleQueue<type>::Length() const {
    if (this->_rear == -1 && this->_front == -1) {
        return 0;
    }

    return (_rear - _front + 1 + _capacity) % _capacity;
}

template<typename type>
std::ostream &operator<<(std::ostream &out, const CircleQueue<type> &src) {
    out << "The size of circle queue: " << src.Length() << std::endl;

    for (int i = 0; i < src.Length(); i++) {
        int actual_index = (src._front + i + src._capacity) % src._capacity;
        out << src._data[actual_index] << std::endl;
    }

    return out;
}

#endif// _QUEUE_CIRCLEQUEUE_H_